This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (4)

3
votes
1answer
43 views

Closed form for series $\sum_{m=1}^{N}m^n\binom{N}{m}$

How can we calculate the series $$ I_N(n)=\sum_{m=1}^{N}m^n\binom{N}{m}? $$ with $n,N$ are integers. The first three ones are $$ I_N(1)=N2^{N-1}; I_N(2)=N(N+1)2^{N-2}; I_N(3)=N^2(N+3)2^{N-3} $$
1
vote
2answers
29 views

Stars & Bars Question: Identical Balls in Distinct Boxes

I am terrible at combinatorics so any and all help would be appreciated. 20 identical balls are put into 10 distinct boxes so that at most 3 boxes are empty. In how many ways can this be done? ...
1
vote
1answer
22 views

Reference request: comprehensive handbook of combinatorial formulae

I am searching for an handbook that collects a comprehensive list of formulae in combinatorics. Could you point out one such reference?
1
vote
2answers
29 views

How many $6$-permutations of $[15]$ have their digits listed in increasing order?

$[15]$ is the set of first $15$ naturals. In my textbook permutation means a sequence without repetition. There are $15 \cdot 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10$ permutations. For each word like ...
2
votes
1answer
46 views

How many different regular icosahedra can be made by assigning numbers from 1 to 20 to the faces?

"How many different regular icosahedra is it possible to make assigning numbers from 1 to 20 to its faces? Suppose all faces indistinguishable." I was trying to solve it as following: the total ...
0
votes
0answers
10 views

Combinatorial definition of Hall–Littlewood polynomials (sum over SSYT?)

Hall–Littlewood polynomials $P_\lambda(x;t)$ is an important deformation of Schur polynomials forming a basis in the ring of symmetric polynomials over $\mathbb Z[t]$. There are various definitions, ...
0
votes
0answers
10 views

Is there any study on noncrossing partitions for cyclic polytopes?

I am from another area of maths, and has never learnt combinatorics and polytope theory properly before, so please feel free to point out any mistake/misuse of terminology. The starting point is the ...
-1
votes
0answers
16 views

Find the exponential generating function for the number of symmetric n × n permutation matrices. [on hold]

Find the exponential generating function for the number of symmetric $n × n$ permutation matrices.
0
votes
0answers
32 views

Number of topologies on a set

Let $X$ be a nonempty set with $n$ elements. I want to find an upper bound for the number of possible topologies for $X$. I proceed as follows: The power set $\mathcal P(X)$ contains $2^n$ elements. ...
1
vote
2answers
23 views

Permutations and Combinations Doubt

Question: How many words, with or without meaning, can be made using the letters of the word DEBOTRI such that there are always two letters between D and E? I got $4 \times 2 \times 5P_5 = 960$, ...
0
votes
0answers
26 views

Number of words that can be formed using the word PHILOSOPHY [duplicate]

In the word PHILOSOPHY how many words would have the letters H,I,S,Y together when words are formed by using all 10 letters? ...
4
votes
0answers
20 views

Number of valid NxN Takuzu Boards a.k.a 0h h1 (details inside)?

Takuzu a logic puzzle which has a NxN grid filled with zero's and one's following these rules: 1) Every row/column has equal number of 0's and 1's 2) No two rows/columns are same 3) No three ...
2
votes
1answer
38 views

How to use $\binom a k = \frac{\alpha(a-1)(a-2)\cdots(a-k+1)}{k(k-1)(k-2)\cdots 1}$ to check that ${-1\choose 0}=1$?

I'm trying to use the binomial coefficient: $$\binom{x}k=\begin{cases} \frac{x^{\underline k}}{k!},&\text{if }k\ge 0\\\\ 0,&\text{if }k<0\;, \end{cases}$$ To check that ${-1\choose 0}=1$. ...
4
votes
1answer
94 views

Additive function $f: \mathbb{Z}^\infty \rightarrow \mathbb{Z}$ is zero everywhere.

Let $f: \mathbb{Z}^\infty \rightarrow \mathbb{Z}$ be an additive function ($f(x+y)=f(x)+f(y)$ for every $x,y \in \mathbb{Z}^\infty$). In addition for every $x=(0,\dots, 0,1,0, \dots)$ we have ...
1
vote
1answer
22 views

How to use $\binom a k = \frac{\alpha(a-1)(a-2)\cdots(a-k+1)}{k(k-1)(k-2)\cdots 1}$ to check that $ {-n \choose -n}=0$?

I am trying to use this definition of the binomial coefficient: $$\binom \alpha k = \frac{\alpha^{\underline k}}{k!} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-[k-1])}{k(k-1)(k-2)\cdots 1}$$ To ...
1
vote
1answer
65 views

Why $ {-1\choose 3}=-1$?

Having the following definition: $$\binom \alpha k = \frac{\alpha^{\underline k}}{k!} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k(k-1)(k-2)\cdots 1}\tag{1}$$ Why $\bbox[1px,border:1px ...
7
votes
1answer
56 views

What is the generating function to calculate the number of functions $f:\{1,2,3,4,5,6,7,8,9,10\}\to\{1,2,3,4,5,6,7\}$ with $|Im(f)|=4$?

What is the generating function to calculate the number of functions $f:\{1,2,3,4,5,6,7,8,9,10\}\to\{1,2,3,4,5,6,7\}$ with $|Im(f)|=4$? I've tried these: $$\sum_{k=1}^{10}x^k \cdot ...
0
votes
1answer
16 views

About counting $n$ - digit binary numbers

Here's the problem: You flip a coin $20$ times and record the ordered sequence of heads and tails. How many sequences are there in which you get heads on (at least) flip #$1$, #$4$, #$7$, and ...
2
votes
1answer
30 views

Burnside's lemma simple use

Let's say that $D_3$ acts on a bracelet of 3 beads (Denote S), each bead can be Black or White. I want to count the number of different bracelets (4 - I believe) But using burnside's lemma I get ...
0
votes
2answers
46 views

Sum of binomial coefficients $\sum _{ x=r-2 }^{ n-2 } \binom{x}{r-2}$

$$\sum _{ x=r-2 }^{ n-2 } \binom{x}{r-2}$$ I can't find the sum of the following series. I would appreciate if anyone can show me this problem's solution.
0
votes
1answer
13 views

Counting sequences with certain elements fixed

You flip a coin $20$ times and record the ordered sequence of heads and tails. How many sequences are there in which you get heads on (at least) flip #$1$, #$4$, #$7$, and #$13$? Looks like we ...
1
vote
2answers
38 views

Number of $r$-sided polygons in $P$ with no common edges

We have a $n$-sided convex polygon $P$. How many $r$-sided polygons $(r<n)$, with its vertices among those of $P$, can be formed such that it has no sides (edges) in common with $P$? I tried ...
0
votes
3answers
62 views

If you attempt to predict a Roulette wheel $n$ times, what's the probability you'll get $5$ in a row at some point?

I'm talking about a Roulette wheel with $38$ equally probable outcomes. Someone mentioned that he guessed the correct number five times in a row, and said that this was incredible because the ...
6
votes
2answers
62 views

Is there a “counting groups/committees” proof for the identity $\binom{\binom{n}{2}}{2}=3\binom{n+1}{4}$?

This is exercise number $57$ in Hugh Gordon's Discrete Probability. For $n \in \mathbb{N}$, show that $$\binom{\binom{n}{2}}{2}=3\binom{n+1}{4}$$ My algebraic solution: ...
4
votes
4answers
139 views

Combinatoric proof for $\sum_{k=0}^n{n\choose k}\left(-1\right)^k\left(n-k\right)^4 = 0$ ($n\geqslant5$)

I'm trying to proove the following: $For\space every\space n \ge 5$: $$\sum_{k=0}^n{n\choose k}\left(-1\right)^k\left(n-k\right)^4 = 0$$ I've tried cancelling one $(n-k)$, and got this: ...
0
votes
1answer
20 views

Recognizing when to count multisets [on hold]

Right now I am learning how to recognize counting problems. So far it seems straightforward to recognize problems where we need to count permutations with or without repetitions and subsets. In ...
-3
votes
1answer
25 views

Computing an explicit sum of binomial coefficients [Boxing Day Bonus!…] [on hold]

Seasonings greetings to you all! Can anybody decipher this formula in layman’s terms with an actual numbered answer! forgive my lack of mathematical terminologies (still learning) $$ \binom{25}{10} ...
26
votes
1answer
712 views

X'mas Combinatorics

Inspired the various** algebraic X'mas greetings sent to me over the festive period, I thought I would try to devise one of my own. $$\Large ...
-4
votes
0answers
29 views

Sequence and Divisibility [on hold]

Consider a sequence $a_1$, $a_2$, ..., $a_9$, $a_{10}$, with $a_1=a_{10}$, such that for $i \neq j$, $a_ia_j$ is divisible by $n$ if and only if $|i-j| \neq 1$. What is the minimum value of $n$?
0
votes
1answer
40 views

What is the probability of a chain of a given length in a random graph?

Let $G$ be an undirected graph with $n$ nodes. An edge is randomly and independently drawn from each node to any of the other nodes. If some arbitrary node $a$ is chosen, what is the probability that ...
2
votes
2answers
32 views

Using combinatorics to calculate at least one with 0

Problem is like this: Telephone number consists of $8$ digits. The first digit is not permitted to be $0$ or $1$. Question: how many of the telephone numbers contain at least one zero? I thought if ...
1
vote
0answers
16 views

Expansion for r-associated Stirling numbers of the second kind

I am looking for a paper or guidance for expanding the r-associated Stirling numbers of the second kind $S_r(n,k)$. $S_r(n,k)$ is the number of ways to partition a set of n objects into k subsets, ...
1
vote
4answers
43 views

Number of 6 digit numbers with digits 1,2,3,4 with each digit appearing at least once.

Find the number of 6 digit numbers that can be made with the digits 1,2,3,4 if all the digits are to appear in the number at least once. This is what I did - I fixed four of the digits to be 1,2,3,4 ...
1
vote
1answer
44 views

Pigeon-Hole Problem

Let $p$ and $q$ be two positive integers so that the largest common divisor of $p$ and $q$ is 1. Prove that for any non-negative integers $s\leq p-1$ and $t\leq q-1$, there exists a non-negative ...
0
votes
3answers
18 views

About seemingly similarly posed counting questions

A permutation problem is a problem in which you are asked to count the number of permutations having $k$ symbols in some alphabet of $n$ symbols. How is that different from the question below? ...
2
votes
2answers
50 views

Formula for Heads or tails task

Someone offers you this: "We toss a coin and we pick heads or tails. Whenever you are the winner - I give you \$1.1 (one dollar and ten cents). Whenever I am the winner - you give me \$1 (one ...
1
vote
1answer
30 views

Finding the count of paths with K turns from corner to corner in a square box

I'm having trouble understanding the solution given for the problem here: http://www.codechef.com/DEC11/problems/MOVES/ Given a square table sized $N \times N$ ($3 ≤ N ≤ 5000$; rows and columns ...
0
votes
1answer
22 views

How many $k$-regular bipartite graphs can I make given $n$ distinct vertices?

I'm attempting to solve a problem that I think can be solved best with graph theory. I know very little regarding graph theory, so excuse any misuse of vocabulary (which I only picked up in the last ...
0
votes
3answers
34 views

Urn problem with balls [on hold]

Say you have $2n$ black balls and an additional blue and a red ball. If there exist two urns and you randomly throw $n+1$ balls in each, then what is the probability that you do not have both the ...
1
vote
1answer
51 views

Xmas Special: 25 identical sweets shared between two indivuduals and…

Ready?.. 25 identical sweets must be shared bewteen 1 boy & 1 girl. Each of the children MUST recieve at least 10 sweets each. all sweets must be distrubuted. order not important although I will ...
6
votes
1answer
103 views

On solutions of an equation in $\mathbb{Z}_3$

For integer numbers $x_1, x_2, y_1, y_2, y_3$ suppose that $$ x_1 + x_2 \equiv y_1 + y_2 + y_3 \pmod 3. $$ For $k=0, 1, 2$ define $$ s_k = \Big| \{ y_i \,|\, y_i \equiv k \pmod 3 \} \Big| - \Big| ...
0
votes
3answers
24 views

Difference between 2 different kinds of counting problems both of which can be solved by Product Rule

$1.$ A gymnastics team has $7$ members. The coach must assign one member to compete in each of the $4$ event finals (floor exercise, balance beam, vault, uneven parallel bars). How many different ...
1
vote
1answer
52 views

Pattern on polynomials disguising as exponentials

Recently I've been looking at integer sequences that look like exponential at the first few terms but is actual polynomial, like these two sequences [1] [2]. And there seems to be something ...
0
votes
2answers
71 views

Prove that $F_n={n-1 \choose 0 }+{n-2 \choose 1 }+{n-3 \choose 2 }+\ldots$ where $F(n)$ is the $n$-th fibonacci number [duplicate]

If $F_n$ is the $n$-th fibonacci number, then prove that, $$F_n={n-1 \choose 0 }+{n-2 \choose 1 }+{n-3 \choose 2 }+\ldots$$ I tried the idea of using Pascal's triangle, but it seems to need some ...
1
vote
3answers
31 views

Distributing $N$ distinct objects in $R$ distinct boxes when order matters

There are $P(r+n-1,r-1)$ ways to distribute $n$ objects in $r$ boxes when the order of objects in each box matters. I tried to find out why but I failed. when the order of objects in each box doesn't ...
3
votes
0answers
49 views

Asymptotics of integer compositions

A (weak) composition of a positive integer $n$ into $k$ parts is an ordered sequence of nonnegative integers $(a_1, a_2, \ldots, a_k)$ such that $ \sum_{i=1}^k a_i = n $. I am interested in the case ...
0
votes
1answer
27 views

Prove that a function is total, surjective, injective and find its domain of definition

Let $D = \{1,2,3,4,5,6,7,8,9,10\}$ Let $f:P(N) \to P(N)$, $f(B) = B \triangle D$ I said that the image of this function is: $P(N)$, is that right? It's pretty clear that this function is total ...
2
votes
0answers
25 views

How many 5-character passwords can be made from 5 characters with joins?

Suppose a standard combination lock on a door has 5 distinct buttons (labelled e.g. 1, 2, 3, 4, 5). A passcode is defined by 5 button presses. Buttons can be repeated, so e.g. (5,5,5,5,5), ...
5
votes
2answers
52 views

Are “Balls in Bins” and “Stars and bars” the same?

I want to know that if Balls in Bins and Stars n Bars problems in combinatorics are similar? Can we reduce one into other? How? How can they be mapped to each other?
0
votes
0answers
31 views

Standard problem of Balls and Bins

A general classification of balls and boxes problems in combinatorics in 12 ways. There are 12 categories since 1. Balls may be distinguishable or indistinguishable; 2. Boxes may be distinguishable or ...