For 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)

0
votes
2answers
30 views

Probability of multiple dice rolls with constraints

I am having problems understanding how to tackle part b of the following question. A fair die is rolled three times. What is the probability that A) her second and third rolls are both larger ...
1
vote
0answers
32 views

Setting two variables equal in a multivariable holonomic function

If $f(x,y)$ is a holonomic (a.k.a. $D$-finite: https://en.wikipedia.org/wiki/Holonomic_function) function of two complex (or real) variables, is $g(x)=f(x,x)$ also holonomic?
0
votes
2answers
37 views

Probability for getting -1 in a game of rolling die

In a game, a fair die is rolled. If the result is 1 or 2, you can get 2 points. If the result is 3 or 4, you get -1 points. If the result is 5 or 6, you get 0 points. Now you can roll the die for 6 ...
0
votes
1answer
100 views

Applications of combinations with repetition

I am having problems understanding how to distinguish some combinatorial questions (specifically question 2 below). What distinguishes these two types of questions? In question 1, I can see that ...
3
votes
1answer
99 views

Number of partitions of a set into subsets of cardinality $k$.

I suppose that this question has already been asked, but I couldn't find it. Suppose we have a set $A$ with $nk$ elements. How many partitions of this set into sets of k elements are there?. For ...
3
votes
0answers
113 views

Combinatorial problem about splitting a finite set of real numbers

Given a finite set $X$ of real numbers greater than one. I'm looking for disjoint sets $A,B$ such that $X=A\cup B$ and such that $$\prod_{x\in A}x\leq\prod_{x\in B}x\,.$$ Especially am I interested ...
1
vote
3answers
34 views

Newton formula with out using induction

Is there a way to show that $$(a+b)^n=\sum_{k=0}^n \binom{n}{k}a^kb^{n-k}$$ where $a,b$ are positif integer with out using induction ?
3
votes
0answers
83 views

Class of all graphs with invertible adjacency matrices

This question is a generalization of the question asked here. From the answers of the questions, I can list four classes of graphs which have invertible adjacency matrices. The class of graphs ...
4
votes
0answers
136 views

Parity of a Permutation and Shifting

Given a permutation $P$ of $[1,2,...,n]$ and a positive integer $t\le n$. An operation is defined as shifting any $t$ consecutive elements of $P$ cyclically to the right by one index. For example: ...
1
vote
1answer
37 views

Problem of color painting

Each of $6$ points in space is connected to the other $5$ points by line segments.Each segment thus formed is colored greed or purple.Show that it is impossible to color all the segments without ...
3
votes
2answers
91 views

Combinatorial interpretation of convergent series

Given a series $$ \sum_{n=0}^\infty c_n x^n$$ that converges to $$ {1\over (1-x-x^{17}+x^{18})}$$ I am asked to give a combinatorical interpretation of $c_{10}$, more specifically in regards to a ...
6
votes
2answers
83 views

Rank of a matrix of binomial coefficients

This question arose as a side computation on error correcting codes. Let $k$, $r$ be positive integers such that $2k-1 \leqslant r$ and let $p$ a prime number such that $r < p$. I would like to ...
0
votes
1answer
42 views

find recurrence relation such that you have n digit sequence of $1$'s and $2$'s such that you have at least one instance of consecutive 2's [duplicate]

I let $a_n$ be the different sequences with $n$ digits such that there is at least one instance of consecutive $2$'s. This is what I did, if I place a a $1$ first, I have $n-1$ digits left and by ...
0
votes
2answers
130 views

Lottery payout with organizer margin.

Assume we have a lottery with payouts like this $(1,2,3,4,5,25,30,100)$ So you buy a ticket and you can win a pot which will multiply your ticket price by the numbers written ahead. The organizer ...
1
vote
1answer
30 views

Choose unique numbers from different sets

Suppose that there are n, possibly equal, non-empty sets. The problem is concerning choosing unique n numbers such that first ...
1
vote
1answer
38 views

The number of 3-digit numbers formed using the digits in set $S=\left\{0,1,2,3,4,5\right\}$,so that the digits either increase or decrease

The number of 3-digit numbers formed using the digits in set $S=\left\{0,1,2,3,4,5\right\}$,so that the digits either increase or decrease,is $(A)24\hspace{1cm}(B)30\hspace{1cm}(C)45\hspace{1cm}(D)56$ ...
0
votes
2answers
57 views

Number of ways of scoring a total of 20 runs in one over of six balls

A batsman can score $0,2,3$ or $4$ runs for each ball he receives.If $N$ is the number of ways of scoring a total of 20 runs in one over of six balls.Then find $N$. Different options of scoring ...
0
votes
3answers
110 views

Addresses in decimal,binary,octal and hexadecimal

One of the first minicomputers, the PDP-8 had a word size of 12 bits. (Recall the word size of a computer refers to the number of bits used to encode addresses.) what was the last address in this ...
2
votes
3answers
421 views

How many 3 digit odd numbers greater than 600 can be formed using the digits(2,3,4,5,6 and 7)? [closed]

In my worksheet the answer is 20 but i keep getting a different answer
0
votes
2answers
55 views

Number of ways to put $n$ red cards and $k$ black cards into $4$ distinct jars so that every jar has a card.

So if we define two functions $f_1 [n]\rightarrow [4]$ and $f_2[k]\rightarrow [4]$, in order to do this problem we need for the functions to be onto. This is simple enough, right? If $f_1$ is onto ...
1
vote
1answer
77 views

In how many ways can we select $x$ distinct candies from a collection of $n$ candies of distinct types? [closed]

Suppose we have k distinct types of jars. Lets name these jars as jar1 , jar2 , jar3....jark Now each jar have some candies. A jar will have same type of candies. Moreover no two jars have same ...
1
vote
0answers
21 views

Yet another curious convolution

Some time ago, I found the following algorithmic problema: Count the number of distinct unrooted, unordered, labeled trees of $n$ nodes where each node has at most $k$ neighbors. Given that the ...
0
votes
1answer
34 views

Optimization of shopping list by condition

I am a computer science student that is struggling with a problem of mathematical nature. Thus far I have only studied calculus, discrete mathematics and linear algebra, but cannot figure out how to ...
3
votes
1answer
70 views

Ants moving on a grid

I got asked this as a programming interview question so the "correct" solution is via simulation, but I'm curious about the existence of an analytic solution. Two ants start in opposing corners of ...
7
votes
2answers
205 views

Coloring the windmill

A windmill has $5$ wings and each of these is symmetrically connected to the axis and consists of two parts. If on the wings of the windmill $4$ parts are colored black, $3$ parts are colored red, ...
1
vote
1answer
21 views

Permutation in which the $A's$ appear together in a block of $4$ letters or the $B's$ appear together in a block of $3$ letters

The number of permutation of all the letters $AAAABBBC$ in which the $A's$ appear together in a block of $4$ letters or the $B's$ appear together in a block of $3$ letters is : ...
0
votes
0answers
19 views

What is the complexity of comparing two #P-complete counts?

Given a counting problem with complexity #P-Complete and two inputs $X_1, X_2$, what is the complexity of deciding whether the count for $X_1$ is greater than, less than, or equal to the count for ...
2
votes
0answers
28 views

Derangements of numbers

How many ways can the integers $\{1, . . . , 5\}$ be arranged so that exactly $2$ of elements are in their natural position? Can you generalize this to the integers $\{1, 2, ..., n\}$ so that ...
2
votes
2answers
41 views

How many such strings are there?

How many 50($=n$) digit strings($=f(n)$) composed of only zeros and ones are there such that all "ones" should be in groups of at least 3(The grouping should be explicit), if they occur and must be ...
4
votes
2answers
63 views

Find number of functions such that $f(f(a))=a$

Let X ={1, 2, 3, 4}. Find the number of functions $f : X \rightarrow X$ satisfying $f(f(a)) = a$ for all $1 \le a \le 4$. I took the $f(x) =x$ and, then there are 1 possibilities. But answer is given ...
6
votes
4answers
196 views

how many permutations of {1,2,…,9}

How many permutations of {1,2,…,9} are there such that 1 does not immediately precede 2, 2 does not immediately precede 3, and so forth up to 8 not immediately preceding 9? One obvious example of such ...
1
vote
1answer
113 views

How many triangles can be formed from the 12 non-collinear points?

There are 12 distinct non-collinear points in a same plane, they are points A,B,....L. How many different triangle can be formed, with criteria one of its vertice must be contain point A? My ...
0
votes
1answer
21 views

Offset switch partitions

Say we have 6 tiles numbered: $$ \begin{array}{|c|c|c|c|c|c|} \hline 6&5&4&3&2&1\\ 0&1&2&3&4&5\\ \hline \end{array} $$ You must pick one of the numbers from ...
0
votes
1answer
24 views

Little Graph Theory Problem

Let $G$ be a finite graph and let $H_1,\ldots, H_n$ be some distinct subgraphs with the same number of vertices, and with the property that each edge of $G$ belongs to the same number of the $H_i$. ...
4
votes
2answers
161 views

Seeking a combinatorial proof $\sum _{k=0}^n (n-2k)^2\binom{n}{k}=n\times 2^n$

I would appreciate if somebody could help me with the following problem Q: Seeking a combinatorial proof $(\binom{n}{k}=\frac{n!}{k! (n-k)!} )$ $$\sum _{k=0}^n (n-2 k)^2 \binom{n}{k}=n\times 2^n$$
3
votes
1answer
35 views

Expected value of distinct balls

My friend posed me the following question: We have a bowl with 70 balls, 7 colors, and 10 balls in each color. You draw 20 balls simultaneously from the bowl. What is the expected number of ...
0
votes
1answer
79 views

A question about the proof of the “Lazy caterer's sequence”

A question about the proof of the “Lazy caterer's sequence” In https://en.wikipedia.org/wiki/Lazy_caterer%27s_sequence , Wiki provides formulas:- The maximum number p of pieces that can be created ...
1
vote
2answers
54 views

How many solutions does the equation x + y + w + z = 15 have if x, y, w, z are all non-negative integers?

Combinatorics question: What I tried for solving this problem is (16 - 1 + 4 choose 4). I got 16 from the numbers 0 thought 16 as possible values for x, y , w or z. However apparently the answer is ...
3
votes
0answers
89 views

Square of hockey stick identity: $\sum_{i=r}^n{i \choose r}^2$

Evaluate $\sum_{i=r}^n{i \choose r}^2$ where $n,r\in \mathbb{N},n>r$. This looks like the hockey stick identity but I can't find a way to evaluate it without a computer. Can someone help me out?
0
votes
0answers
42 views

How to use the principle of Inclusion and Exclusion to prove this [duplicate]

I want to show that the number of ways the integers $1, 2, ..., n$ can be arranged in a line so that none of the patterns $12, 23, ..., (n−1)n$ occurs is $d(n) + d(n-1)$ where $d(n)$ is the numbers of ...
0
votes
3answers
36 views

proof for binomial probabilty distribition

Taking one of the example I have learned for binomial probability distribution A fair die is thrown four times. calculate the probability of getting exactly 3 Twos (source) Answer can be obtained ...
2
votes
2answers
62 views

Loaded die probability

The loaded die has the following probabilities: $0.3,0.2,0.1,0.1,0.2,0.1$ for $1,2,3,4,5,6$ respectively. The question asks What is the probability of rolling at least one $1$ and no $2's$ in $4$ ...
1
vote
1answer
41 views

Striling numbers of the first kind $S(m,m-1)$

I want to derive a formula for $S(m,m-1)$ where $S(m,n)$ is the number of ways to seat $m$ people at $n$ circular tables with at least one person at each table, The arrangements at any one ...
0
votes
0answers
14 views

Find the maximum possible cardinality of collection of set

Suppose $B = \{B_1, B_2, \dots, B_k\}$ is an arbitrary collection of 3-element subsets of $n$-element set such that $|B_i \cap B_j| \neq 1$ for each pair of indices $1 \leq i, j \leq k$. Find the ...
2
votes
1answer
46 views

How to give a combinatorial proof for this forumula

I need to give a combinatorial argument that $$S(n,m) = \sum_{i =0} ^{n-1} {n -1 \choose i} S(i,m-1)$$ Where $S(n,m)$ is the Stirling numbers of the second kind. Here is my attempt. Well first ...
0
votes
3answers
69 views

Summation of double choose functions

Are there any identities that deals with a summation like $\sum_{i=0}^{9} {12-i\choose3}{3+i\choose3}$.
1
vote
1answer
55 views

A classic stars and bars problem

We have $n$ spaces to be filled with stars or bars. How many ways are there to do this using $k \space (k<n/2)$ stars if between every two star there has to be at least one stick? Also, how many ...
1
vote
1answer
41 views

Different colors possibilities

I am given $n$ number of candies . And candies can be any one of the $k$ colors i.e. there are candies of $k$ different colors . How many possibilities are there such that on each selection of any ...
3
votes
1answer
38 views

Maximum number of points of intersection of the perpendiculars

There are $5$ points in a plane. Let $m$ denote the maximum number of intersections of the perpendiculars drawn from each point to the lines joining the other points. Find $m$. Can I get a visual ...
1
vote
1answer
34 views

A question on how many doors will be open? [duplicate]

My friend gave me a question. The question states: There a $100$ people named $(1,2,3,.....,100)$ and there are $100$ doors named $(1,2,3,...,100)$ .Assume all doors are closed. The first named $1$ ...